﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Jenvin.Library.DataStruct
{
    /// <summary>
    /// 小顶堆优先队列 插入push ,pop的时间复杂度都的O(log n)
    /// pop 出来的是一个从小到大的序列。
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class PriorityQueue<T>
    {
        protected class DelegateComparer<T1> : IComparer<T1>
        {
            private Comparison<T1> m_comparison = null;
            public DelegateComparer(Comparison<T1> comparison)
            {
                if (comparison == null)
                    throw new ArgumentNullException("comparison");
                this.m_comparison = comparison;
            }

            #region IComparer<T> 成员

            public int Compare(T1 x, T1 y)
            {
                return m_comparison(x, y);
            }

            #endregion
        }
        protected int size;
        private int maxSize;
        protected internal T[] heap;
        protected internal IComparer<T> m_comparer = null;
        /// <summary>
        /// size 为容量大小
        /// </summary>
        /// <param name="size"></param>
        public PriorityQueue(int size)
            : this(size,(IComparer<T>)null)
        {

        }

        public PriorityQueue(int size, Comparison<T> comparison)
        :this(size,new DelegateComparer<T>(comparison))
        {
         
        }
        public PriorityQueue(int size, IComparer<T> comparer)
        {
            if (comparer == null || comparer == Comparer<T>.Default)
                m_comparer = Comparer<T>.Default;
            else
                m_comparer = comparer;

            Initialize(size);
        }
        protected void Initialize(int maxSize)
        {
            size = 0;
            int heapSize;
            if (0 == maxSize)
                heapSize = 2;//0 位不用。分配一个额外的单元，避免不必要的if 语句判断
            else
                heapSize = maxSize + 1;
            heap = new T[heapSize];
            this.maxSize = maxSize;
        }

        /// <summary>
        /// 如果有空位 ，直接插入，返回default(T)
        /// 如果没空位。且插入的元素大于堆顶元素。将堆顶元素替换。并反加被替换的过元素
        /// 否则，直接返回传入元素，不做任何操作
        /// </summary>
        /// <param name="elem"></param>
        /// <returns></returns>
        public T Push(T elem)
        {
            if (size < maxSize)//如果有空位 ，直接插入
            {
                size++;
                heap[size] = elem;
                UpHeap();
                return default(T);
            }
            else if (size > 0 && m_comparer.Compare(elem, heap[1]) > 0)
                //如果插入的元素大于堆顶元素。将堆顶元素替换
            {
                T ret = heap[1];
                heap[1] = elem;
                DownHeap();
                return ret;
            }
            else
            {
                return elem;
            }
        }

        public T Pop()
        {
            if (size > 0)
            {
                T result = heap[1]; // save first value
                heap[1] = heap[size]; // move last to first
                heap[size] = default(T); // permit GC of objects
                size--;
                DownHeap(); // adjust heap
                return result;
            }
            else
                return default(T);
        }

        /// <summary> 返回堆顶元素出队列</summary>
        public T Top()
        {
            return heap[1];
        }        
        /// <summary>返回大小 </summary>
        public int Size()
        {
            return size;
        }

        /// <summary>
        /// 重新调整堆.当元素未满时，是在堆尾放入数据。
        /// 而不是堆顶，因此需要做一次从下往上的调整
        /// </summary>
        protected void UpHeap()
        {
            int i = size;
            T node = heap[i]; //堆尾的元素
            int j = URShift(i, 1);//父结点
            while (j > 0 && m_comparer.Compare(node, heap[j]) < 0)
            {   //如果父结点比它大。
                heap[i] = heap[j]; //将父结点调下来
                i = j;//继续调整到根元素
                j = URShift(j, 1);
            }
            heap[i] = node; // install saved node
        }
        /// <summary>
        /// 除
        /// </summary>
        /// <param name="number"></param>
        /// <param name="bits"></param>
        /// <returns></returns>
        protected int URShift(int number, int bits)
        {
            return (int)(((uint)number) >> bits);
        }

        /// <summary>
        /// 重新调整堆.从上往下。
        /// 在顶元上插入数据。导致堆乱序，做一次调整堆的操作。
        /// 大的沉下去，小的升上来
        /// </summary>
        protected void DownHeap()
        {
            int i = 1;
            T node = heap[i]; //heap[1] 是堆顶是元素
            int j = i << 1;
            int k = j + 1;
            //在左，还是在右 。小于则是左子树。大于右子树
            if (k <= size && m_comparer.Compare(heap[k], heap[j]) < 0)
            {   //选出小的哪个子树
                j = k;
            }

            while (j <= size && m_comparer.Compare(heap[j], node) < 0)
            {
                heap[i] = heap[j]; // shift up child
                i = j;
                j = i << 1;//左。
                k = j + 1; //右
                if (k <= size && m_comparer.Compare(heap[k], heap[j]) < 0)
                {
                    j = k;
                }
            }
            heap[i] = node; // 对掉。将堆顶元素放到找到位置
        }
    }
}
